package list

import (
	"container/list"
	"sort"
)

type List[T any] struct {
	l    *list.List
	less func(T, T) bool
}

type Element = list.Element

func New[T any](less func(T, T) bool) *List[T] {
	return &List[T]{l: list.New(), less: less}
}

func (x *List[T]) Len() int { return x.l.Len() }

func (x *List[T]) Swap(i, j int) {
	if i == j {
		return
	}
	ei, ej := x.Index2(i, j)
	if ei != nil && ej != nil {
		ei.Value, ej.Value = ej.Value, ei.Value
	}
}

func (x *List[T]) GetValue(e *Element) T {
	if e != nil {
		if v, ok := e.Value.(T); ok {
			return v
		}
	}
	var r T
	return r
}

func (x *List[T]) Less(i, j int) bool {
	if i == j || x.less == nil {
		return false
	}
	ei, ej := x.Index2(i, j)
	if ei != nil && ej != nil {
		return x.less(x.GetValue(ei), x.GetValue(ej))
	}
	return false
}

func (x *List[T]) _less(i, j T) bool {
	if x.less == nil {
		return false
	}
	return x.less(i, j)
}

func (x *List[T]) Front() T {
	e := x.l.Front()
	return x.GetValue(e)
}

func (x *List[T]) Back() T {
	e := x.l.Back()
	return x.GetValue(e)
}

func (x *List[T]) Begin() *Element {
	return x.l.Front()
}

func (x *List[T]) ReverseBegin() *Element {
	return x.l.Back()
}

func (x *List[T]) Index(i int) *Element {
	e := x.Begin()
	for e != nil && i > 0 {
		e = e.Next()
		i--
	}
	return e
}

func (x *List[T]) Index2(i int, j int) (*Element, *Element) {
	if i > j {
		ej, ei := x.Index2(j, i)
		return ei, ej
	}
	ei := x.Begin()
	j -= i
	for ei != nil && i > 0 {
		ei = ei.Next()
		i--
	}
	ej := ei
	for ej != nil && j > 0 {
		ej = ej.Next()
		j--
	}
	return ei, ej
}

func (x *List[T]) Find(v T) *Element {
	return x.FindFunc(v, func(l, r T) bool {
		return !x._less(l, r) && !x._less(r, l)
	})
}

func (x *List[T]) FindFunc(v T, eq func(T, T) bool) *Element {
	return x.FindByFunc(v, x.Begin(), eq)
}

func (x *List[T]) FindBy(v T, start *Element) *Element {
	return x.FindByFunc(v, start, func(l, r T) bool {
		return !x._less(l, r) && !x._less(r, l)
	})
}

func (x *List[T]) FindByFunc(v T, start *Element, eq func(T, T) bool) *Element {
	for e := start; e != nil; e = e.Next() {
		if vv, ok := e.Value.(T); ok {
			if eq(v, vv) {
				return e
			}
		}

	}
	return nil
}

func (x *List[T]) Remove(v T) bool {
	return x.RemoveMuch(v, 1) == 1
}

func (x *List[T]) RemoveMuch(v T, c int) int {
	return x.RemoveMuchFunc(v, c, func(l, r T) bool {
		return !x._less(l, r) && !x._less(r, l)
	})
}

func (x *List[T]) RemoveAll(v T) int {
	return x.RemoveMuch(v, -1)
}

func (x *List[T]) RemoveFunc(v T, eq func(T, T) bool) bool {
	return x.RemoveMuchFunc(v, 1, eq) == 1
}

func (x *List[T]) RemoveMuchFunc(v T, c int, eq func(T, T) bool) int {
	if c < 1 {
		c = x.Len()
	}
	n := x.Len()
	e := x.Begin()
	for c > 0 && e != nil {
		e = x.FindByFunc(v, e, eq)
		if e == nil {
			break
		}
		c--
		e = e.Next()
	}
	return x.Len() - n
}

func (x *List[T]) RemoveAllFunc(v T, eq func(T, T) bool) int {
	return x.RemoveMuchFunc(v, -1, eq)
}

// 删除一个，返回下一个或者nil
func (x *List[T]) Erase(e *Element) *Element {
	n := x.Len()
	next := e.Next()
	x.l.Remove(e)
	if n == x.Len()-1 {
		return next
	}
	return nil
}

// PushFront inserts a new element e with value v at the front of list l and returns e.
func (x *List[T]) PushFront(v T) *Element {
	return x.l.PushFront(v)
}

// PushBack inserts a new element e with value v at the back of list l and returns e.
func (x *List[T]) PushBack(v T) *Element {
	return x.l.PushBack(v)
}

func (x *List[T]) PopFront() T {
	if x.Len() > 0 {
		v := x.Front()
		x.Erase(x.Begin())
		return v
	}
	var r T
	return r
}

func (x *List[T]) PopBack() T {
	if x.Len() > 0 {
		v := x.Back()
		x.Erase(x.ReverseBegin())
		return v
	}
	var r T
	return r
}

func (x *List[T]) PushFrontMuch(v ...T) {
	for _, a := range v {
		x.PushFront(a)
	}
}

// PushBack inserts a new element e with value v at the back of list l and returns e.
func (x *List[T]) PushBackMuch(v ...T) {
	for _, a := range v {
		x.PushBack(a)
	}
}

// InsertBefore inserts a new element e with value v immediately before mark and returns e.
// If mark is not an element of l, the list is not modified.
// The mark must not be nil.
func (x *List[T]) InsertBefore(v T, mark *Element) *Element {
	return x.l.InsertBefore(v, mark)
}

// InsertAfter inserts a new element e with value v immediately after mark and returns e.
// If mark is not an element of l, the list is not modified.
// The mark must not be nil.
func (x *List[T]) InsertAfter(v T, mark *Element) *Element {
	return x.l.InsertAfter(v, mark)
}

func (x *List[T]) Sort() {
	if x.less != nil {
		sort.Sort(x)
	}
}

// MoveToFront moves element e to the front of list l.
// If e is not an element of l, the list is not modified.
// The element must not be nil.
func (x *List[T]) MoveToFront(e *Element) {
	x.l.MoveToFront(e)
}

// MoveToBack moves element e to the back of list l.
// If e is not an element of l, the list is not modified.
// The element must not be nil.
func (x *List[T]) MoveToBack(e *Element) {
	x.l.MoveToBack(e)
}

// MoveBefore moves element e to its new position before mark.
// If e or mark is not an element of l, or e == mark, the list is not modified.
// The element and mark must not be nil.
func (x *List[T]) MoveBefore(e, mark *Element) {
	x.l.MoveBefore(e, mark)
}

// MoveAfter moves element e to its new position after mark.
// If e or mark is not an element of l, or e == mark, the list is not modified.
// The element and mark must not be nil.
func (x *List[T]) MoveAfter(e, mark *Element) {
	x.l.MoveAfter(e, mark)
}

// PushBackList inserts a copy of another list at the back of list l.
// The lists l and other may be the same. They must not be nil.
func (x *List[T]) PushBackList(other *List[T]) {
	x.l.PushBackList(other.l)
}

// PushFrontList inserts a copy of another list at the front of list l.
// The lists l and other may be the same. They must not be nil.
func (x *List[T]) PushFrontList(other *List[T]) {
	x.l.PushFrontList(other.l)
}
